A host interface that connects to a bus, such as a Peripheral Component Interconnect (PCI) bus, may include a core. The core manages control circuitry responsible for data transfer to and from a device, such as a storage device, coupled to the bus. Data transfer and other commands may be placed in a queue. Commands contained within the queue entry may be skipped or ignored or may fail during processing. When a command is not successfully processed, a validity flag is associated with the queue entry. As processing continues, the core advances from one queue entry to the next, checking the validity flag to determine if the command needs to be reissued. Processing time is easily wasted if there are relatively few commands to be reissued. For example, in a worst-case scenario, the first and last of N queue entries may be the only valid entries, so the core would have to traverse N−2 invalid queue entries to reissue the two commands.
Two prior art solutions have attempted to solve the problem of completed entries intermixed with uncompleted entries in the queue. The first solution, in-order linear traversal of the queue, requires time to process each completed entry and determine if that entry should be skipped. The second solution, Head of List Alternation with a First In First Out memory, is only able to process two entries at a time and absorb completed entries one or two at a time.
Therefore, it would be desirable to provide a more efficient queue traversal method.